1. Field of the Invention
The present invention relates to data storage systems that allocate storage space using bitmaps.
2. Description of the Related Art
Storage systems, particularly systems that store data objects contiguously, often use bitmaps to represent and manage free space. Typically, the value of each bit in a bitmap represents whether a unit of storage, e.g., a block, is free. A bit value of xe2x80x9c1xe2x80x9d in a free space bitmaps indicates that the block associated with the bit is free, and a value of xe2x80x9c0xe2x80x9d indicates that the block is not free. Of course, a used space bitmap would reverse the free/not free values.
Larger storage systems require larger bitmaps, with some bitmaps potentially including many pages. Each page in turn includes many xe2x80x9cwordsxe2x80x9d of bits, with the word size being a power of two and generally being equal to the register width of the processor being used, e.g., 16 bits, 32 bits, 64 bits, and so on. Thus, a processor can read up to the word size number of bits in parallel. When it is time to allocate free space for a data object to be stored, the allocation processor searches the bitmap for a sequence of bits that represents free space which is sufficiently large to store the object.
Bitmaps have several advantages over other management tools such as so-called xe2x80x9cextent listsxe2x80x9d and the xe2x80x9cbuddy systemxe2x80x9d disclosed by Knuth in The Art of Computer Science, Vol. 1. For instance, bitmaps have the advantage of two-way addressing, meaning that the block address of managed space can be used to locate the corresponding bit address in the bitmap and vice-versa. This makes the xe2x80x9cliberationxe2x80x9d of space which is no longer required for storage relatively simple, and it also makes it relatively simple to extend an existing allocation in place. Moreover, bitmaps are self organizing, in that searching for a range of storage is localized to the respective bits in the bitmap that represent the range of storage. Extent lists and buddy systems, in contrast, can become disorganized. Still further, bitmaps are inherently parallel, with one performance advantage over extent lists being that relatively simple latches can be used to synchronize multiple processes over bitmaps, whereas extent lists require the use of more complex locks. Additionally, while the buddy system can quickly find strings of bits representing free space (xe2x80x9cgapsxe2x80x9d), the gaps are constrained to be aligned with power of 2 boundaries, which often results in undesirably splitting larger gaps into plural smaller gaps. This is not as robust as being able to exploit gaps of any size, and at any offset from a reference, a possibility the present invention understands is provided for by bitmaps.
However, the present invention observes that searching bitmaps for data object allocation purposes can be inefficient. For instance, a linear search of a bitmap requires a fixed number of steps to examine each bit, increasing the time it takes to find an allocation. Also, previous systems such as the GPFS/Tiger Shark file system look in only a single bitmap word for an allocation. As recognized herein, some data objects might be sufficiently large to require an allocation that cannot be represented by a single bitmap word. Moreover, by limiting an allocation to spaces represented in only a single bitmap word, an allocation that might span multiple contiguous words that together have a contiguous string of free space bits cannot be considered. The invention disclosed herein addresses one or more of the critical observations set forth above.
A general purpose computer is programmed according to the inventive steps herein to manage storage space in a storage system. The invention can also be embodied as an article of manufacturexe2x80x94a machine componentxe2x80x94that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to execute the present logic. This invention is realized in a critical machine component that causes a digital processing apparatus to perform the inventive method steps herein.
The invention can be implemented by a computer system including a data storage system having a bitmap of bits representing free and used space on a data storage medium, and a processor associated with a data storage system. The processor has logic for receiving a size of an object to be stored, with the size establishing a target number xe2x80x9ckxe2x80x9d of bits in the bitmap. The processor also has logic for, in a first word of bits in the bitmap, determining a suffix sequence of bits when all bit values in the suffix sequence are a predetermined value. In a second word of bits in the bitmap, the processor logic determines a prefix sequence of bits when all bit values in the prefix sequence are the predetermined value. The logic of the processor returns an allocation for the object when the length of the prefix and suffix together equals at least the target number xe2x80x9ckxe2x80x9d of bits.
In another aspect, a computer program device includes a computer program storage device that is readable by a processor. A program is on the program storage device and includes instructions which can be executed by the processor for using a bitmap to allocate space in a data storage system. The program includes computer readable code means for identifying a contiguous number of bits in the bitmap when each bit in the contiguous number has a predetermined value and when the number of bits in the contiguous number is at least as great as a target number xe2x80x9ckxe2x80x9d of bits. The contiguous number of bits span more than a single word in the bitmap.
In still another aspect, a computer-implemented method for identifying a target number xe2x80x9ckxe2x80x9d of storage blocks using a bitmap including words of xe2x80x9cwxe2x80x9d bits each includes identifying, in a first word or words, a suffix having xe2x80x9csxe2x80x9d contiguous bits. Each bit has a predetermined value, e.g., xe2x80x9chighxe2x80x9d. The method also includes identifying, in a second word or words contiguous to or near the first word or words, a prefix having xe2x80x9cpxe2x80x9d contiguous bits. Each bit in the prefix has the predetermined value, and xe2x80x9cpxe2x80x9d and xe2x80x9csxe2x80x9d together equal at least xe2x80x9ckxe2x80x9d.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts, and in which: